// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"math/big"
	"math/bits"
)

// 所以你想计算一些常数c的x/c？
// 机器分割指令很慢，所以我们尝试
// 用乘法+几次运算来计算这个除法
// 其他便宜的指令。
// （这里我们假设c！=0、+/-1或+/-2^i。这些
// 案件易于以不同方式处理）。

// 来自https的技术：

// 首先考虑无符号划分。
// 我们的策略是预先计算1/c，然后执行
// None
// 1/c小于1，所以我们不能直接在
// 整数算术。让我们来计算2^e/c
// 对于e TBD值（^=指数化）。然后
// None
// 除以2^e很容易。不幸的是，e/c不是整数。
// 因此，我们必须对其进行近似计算。我们称之为近似值m。
// 然后我们再计算
// None
// None
// 其中n是单词大小。
// 设置x=c会使c*m>=2^e。
// None
// 剩下的就是选择e。
// 设m=2^e/c+delta，0<=delta<1
// None
// None
// 我们必须有x*delta/2^e<1/c，这样
// None
// 重新安排,，
// 2^e>x*delta*c
// x最多可以是2^n-1，增量最多可以是1。
// 所以2^e>=2^n*c就足够了。
// None
// None
// 由于m中有n+1位，因此会产生额外的复杂性。
// 硬件将我们限制为n位乘以n位。
// 我们将其分为3种情况：
// None
// 案例1:m是偶数。
// None
// None
// None
// None
// 乘+移位
// None
// 案例2:c是偶数。
// None
// None
// None
// s'=s-1
// None
// None
// None
// None
// None
// None
// 移位+乘法+移位
// None
// 案例3：其他一切
// 设k=m-2^n。k适合于n位。
// None
// None
// None
// None
// None
// None
// 乘法+平均值+移位
// None
// 这些可通过以下方式在硬件中实现：
// None
// None
// （不只是常规的添加和移位，因为中间结果
// a+b中有n+1位。然而，这是可以做到的
// 在x86上的2条指令中。）

// umagicOK报告我们是否应该将n位除以c。
func umagicOK(n uint, c int64) bool {
	// 将ConstX auxint值转换为它们表示的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	// 不适用于0。
	// 不要使用2的幂。
	return d&(d-1) != 0
}

// umagicOKn报告是否应将无符号n位除以c。
// 当c=0和c不是2的幂。
func umagicOK8(c int8) bool   { return c&(c-1) != 0 }
func umagicOK16(c int16) bool { return c&(c-1) != 0 }
func umagicOK32(c int32) bool { return c&(c-1) != 0 }
func umagicOK64(c int64) bool { return c&(c-1) != 0 }

type umagicData struct {
	s int64  // None
	m uint64 // None
}

// umagic计算将无符号n位除以常数uint64（c）所需的常数。
// 返回值满足所有0<=x<2^n
// 楼层（x/uint64（c））=x*（m+2^n）>>（n+s）
func umagic(n uint, c int64) umagicData {
	// 将ConstX auxint值转换为它们表示的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	C := new(big.Int).SetUint64(d)
	s := C.BitLen()
	M := big.NewInt(1)
	M.Lsh(M, n+uint(s))     // 2^（n+s）
	M.Add(M, C)             // 2^（n+s）+c
	M.Sub(M, big.NewInt(1)) // 2^（n+s）+c-1
	M.Div(M, C)             // None
	if M.Bit(int(n)) != 1 {
		panic("n+1st bit isn't set")
	}
	M.SetBit(M, int(n), 0)
	m := M.Uint64()
	return umagicData{s: int64(s), m: m}
}

func umagic8(c int8) umagicData   { return umagic(8, int64(c)) }
func umagic16(c int16) umagicData { return umagic(16, int64(c)) }
func umagic32(c int32) umagicData { return umagic(32, int64(c)) }
func umagic64(c int64) umagicData { return umagic(64, c) }

// 对于签名部门，我们使用类似的策略。
// 首先，我们强制执行一个正c。
// x/c=-（x/（-c））
// 对于c<0，这将需要额外的负op。
// None
// 如果x为正，我们处于非常相似的状态
// 对于上面未签名的情况。我们定义：
// None
// None
// 然后
// None
// 如果x是负数，我们有
// None
// （TODO:派生？）
// None
// 乘法有点奇怪，因为它是一个有符号的n位值
// 乘以无符号n位值。对于n小于
// 字号，我们可以适当地扩展x和m，并使用
// 有符号乘法指令。对于n==字长，
// 我们必须使用有符号的乘法高且正确
// 通过添加x*2^n得到的结果。
// None
// 如果x<0，则通过减去x>>（n-1）来添加1。

func smagicOK(n uint, c int64) bool {
	if c < 0 {
		// 对负c不起作用。
		return false
	}
	// 不适用于0。
	// 不要将其用于2的幂。
	return c&(c-1) != 0
}

// smagicOKn报告我们是否应该将有符号n位除以c。
func smagicOK8(c int8) bool   { return smagicOK(8, int64(c)) }
func smagicOK16(c int16) bool { return smagicOK(16, int64(c)) }
func smagicOK32(c int32) bool { return smagicOK(32, int64(c)) }
func smagicOK64(c int64) bool { return smagicOK(64, c) }

type smagicData struct {
	s int64  // None
	m uint64 // None
}

// magic计算将有符号n位除以常数c所需的常数。
// 必须有c>0。
// 返回值满足所有-2^（n-1）<=x<2^（n-1）
// trunc（x/c）=x*m>>（n+s）+（x<0？1:0）
func smagic(n uint, c int64) smagicData {
	C := new(big.Int).SetInt64(c)
	s := C.BitLen() - 1
	M := big.NewInt(1)
	M.Lsh(M, n+uint(s))     // 2^（n+s）
	M.Add(M, C)             // 2^（n+s）+c
	M.Sub(M, big.NewInt(1)) // 2^（n+s）+c-1
	M.Div(M, C)             // None
	if M.Bit(int(n)) != 0 {
		panic("n+1st bit is set")
	}
	if M.Bit(int(n-1)) == 0 {
		panic("nth bit is not set")
	}
	m := M.Uint64()
	return smagicData{s: int64(s), m: m}
}

func smagic8(c int8) smagicData   { return smagic(8, int64(c)) }
func smagic16(c int16) smagicData { return smagic(16, int64(c)) }
func smagic32(c int32) smagicData { return smagic(32, int64(c)) }
func smagic64(c int64) smagicData { return smagic(64, c) }

// 与直接计算相比，可以更有效地检查整除性x%c==0
// 模量x%c，并与0进行比较。
// None
// 同样的“用乘法除以不变整数”的论文
// None
// 沃伦在《黑客的喜悦》第10-17节中进一步阐述了这一点
// None
// 首先要注意的是，对于奇数整数，可以计算精确除法
// 通过使用关于字号2^n的模逆。
// None
// 给定c，计算m，使（c*m）mod 2^n==1
// 然后，如果c除以x（x%c==0），商由q=x/c==x*m mod 2^n给出
// None
// None
// None
// None
// None
// 如果x不能被c整除，那么x*m mod 2^n的值必须大于max。
// None
// None
// 涉及一次乘法和比较。
// None
// 为了将此扩展到偶整数，考虑C＝D0* 2 ^ k，其中D0是奇数。
// 我们可以测试x是否可以被d0和2^k整除。
// 对于d0，测试与上述相同。设m为m*d0 mod 2^n==1
// None
// 被2^k整除的测试是对k个尾随零的检查。
// 注意，由于d0是奇数，m是奇数，因此x*m将具有相同数量的
// 尾随零为x。所以这两个测试是,，
// None
// None
// x*m以k个零位结束
// None
// 这些可以通过以下方式组合成一个比较
// （哈克喜欢的定理ZRU）用于无符号整数。
// None
// None
// 其中RotRight（x，k）是x乘以k位的右旋转。
// None
// None
// 但是由于x以k结尾，所有旋转的位也都是零。
// None
// None
// 如果x不以k个零位结尾，则RotRight（x，k）
// 在k个最高位中有一些非零位。
// None
// None
// None
// None
// None
// 大于a的前n-k位，因为其余x位为零。
// None
// 因此，有关的两个条件可以用单一测试代替
// None
// None
// None
// 其中d0*2^k在右侧被c替换。

// udivisibleOK报告是否应将无符号n位除数检查的强度减少c。
func udivisibleOK(n uint, c int64) bool {
	// 将ConstX auxint值转换为它们表示的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	// 不适用于0。
	// 不要使用2的幂。
	return d&(d-1) != 0
}

func udivisibleOK8(c int8) bool   { return udivisibleOK(8, int64(c)) }
func udivisibleOK16(c int16) bool { return udivisibleOK(16, int64(c)) }
func udivisibleOK32(c int32) bool { return udivisibleOK(32, int64(c)) }
func udivisibleOK64(c int64) bool { return udivisibleOK(64, c) }

type udivisibleData struct {
	k   int64  // 跟踪零（c）
	m   uint64 // m*（c>>k）模2^n==1奇数部分模2^n的乘法逆
	max uint64 // None
}

func udivisible(n uint, c int64) udivisibleData {
	// 将ConstX auxint值转换为它们表示的实际uint64常量。
	d := uint64(c) << (64 - n) >> (64 - n)

	k := bits.TrailingZeros64(d)
	d0 := d >> uint(k) // 除数的奇数部分

	mask := ^uint64(0) >> (64 - n)

	// 通过牛顿法计算乘法逆。
	// 二次收敛使每次迭代的正确位数加倍。
	m := d0            // 初始猜测更正为3位d0*d0 mod 8==1
	m = m * (2 - m*d0) // 6位
	m = m * (2 - m*d0) // 12位
	m = m * (2 - m*d0) // 24位
	m = m * (2 - m*d0) // 48位
	m = m * (2 - m*d0) // 96位>=64位
	m = m & mask

	max := mask / d

	return udivisibleData{
		k:   int64(k),
		m:   m,
		max: max,
	}
}

func udivisible8(c int8) udivisibleData   { return udivisible(8, int64(c)) }
func udivisible16(c int16) udivisibleData { return udivisible(16, int64(c)) }
func udivisible32(c int32) udivisibleData { return udivisible(32, int64(c)) }
func udivisible64(c int64) udivisibleData { return udivisible(64, c) }

// 对于有符号整数，类似的方法如下。
// None
// 给定c>1且奇数，计算m，使（c*m）mod 2^n==1
// 然后，如果c除以x（x%c==0），商由q=x/c==x*m mod 2^n给出
// None
// None
// None
// None
// 因此，x是c的倍数，当且仅当：
// None
// None
// 由于c>1和奇数，这可以通过
// None
// None
// None
// None
// 为了将此扩展到偶整数，考虑C＝D0* 2 ^ k，其中D0是奇数。
// 我们可以测试x是否可以被d0和2^k整除。
// None
// 设m为（d0*m）mod 2^n==1。
// 设q=x*m模2^n。那么c除以x，如果：
// None
// None
// None
// 为了将其转换为一个比较，我们使用以下定理（Hacker的喜悦中的ZRS）。
// None
// 对于>=0，以下条件是等效的：
// 1） -a<=x<=a和x以至少k个0位结束
// None
// None
// 其中a'=a&-2^k（a的右k位设置为零）
// None
// 要查看1和2是否相等，请注意-a<=x<=a相当于
// -a'<=x<=a'当且仅当x以至少k个0位结尾。将-a'添加到每一侧会得到，
// 0<=x+a'<=2a'和x+a'至少以k个0位结束，当且仅当x结束，因为a'已经结束
// 定义为k 0位。我们可以使用上面的定理ZRU，其中x->x+a'和a->2a'给出1）==2）。
// None
// 设m为（d0*m）mod 2^n==1。
// 设q=x*m模2^n。
// None
// None
// 那么可分性测试是：
// None
// None
// None
// 请注意，计算是使用无符号整数执行的。
// 由于a“可以有n-1位，2a”可以有n位，因此没有溢出的风险。

// sdivisibleOK报告我们是否应该将有符号n位除数检查减少c。
func sdivisibleOK(n uint, c int64) bool {
	if c < 0 {
		// 对负c不起作用。
		return false
	}
	// 不适用于0。
	// 不要将其用于2的幂。
	return c&(c-1) != 0
}

func sdivisibleOK8(c int8) bool   { return sdivisibleOK(8, int64(c)) }
func sdivisibleOK16(c int16) bool { return sdivisibleOK(16, int64(c)) }
func sdivisibleOK32(c int32) bool { return sdivisibleOK(32, int64(c)) }
func sdivisibleOK64(c int64) bool { return sdivisibleOK(64, c) }

type sdivisibleData struct {
	k   int64  // 跟踪零（c）
	m   uint64 // m*（c>>k）模2^n==1奇数部分模2^n的乘法逆
	a   uint64 // None
	max uint64 // None
}

func sdivisible(n uint, c int64) sdivisibleData {
	d := uint64(c)
	k := bits.TrailingZeros64(d)
	d0 := d >> uint(k) // 除数的奇数部分

	mask := ^uint64(0) >> (64 - n)

	// 通过牛顿法计算乘法逆。
	// 二次收敛使每次迭代的正确位数加倍。
	m := d0            // 初始猜测更正为3位d0*d0 mod 8==1
	m = m * (2 - m*d0) // 6位
	m = m * (2 - m*d0) // 12位
	m = m * (2 - m*d0) // 24位
	m = m * (2 - m*d0) // 48位
	m = m * (2 - m*d0) // 96位>=64位
	m = m & mask

	a := ((mask >> 1) / d0) & -(1 << uint(k))
	max := (2 * a) >> uint(k)

	return sdivisibleData{
		k:   int64(k),
		m:   m,
		a:   a,
		max: max,
	}
}

func sdivisible8(c int8) sdivisibleData   { return sdivisible(8, int64(c)) }
func sdivisible16(c int16) sdivisibleData { return sdivisible(16, int64(c)) }
func sdivisible32(c int32) sdivisibleData { return sdivisible(32, int64(c)) }
func sdivisible64(c int64) sdivisibleData { return sdivisible(64, c) }
